Asynchronous Transfer Mode (ATM) has been increasingly used for network applications, particularly as interconnected networks grow to a large size. ATM is based on cells of pre-defined length wherein the cells are forwarded from one user or network to another user or network via switches. By directing cells from a source to only an address or addresses of interest, advantages are obtained with regard to overall communication traffic. However, the use of ATM has resulted in the need for new hardware and software.
ATM switches are known which provide a transfer of cells from an input to one of several switch outputs. As the users or networks which are connected by the switch increase, switches of greater size are required.
It would be advantageous to be able to provide ATM switches of any switch capacity without blocking the full bandwidth of the various component switches. It would be desirable to scale bandwidth up or down.
FIG. 1 shows an ATM switch element in its basic form, namely a 2.times.2 switch, with two inputs each connectable to either of two outputs (the switch may also be bi-directional but one direction is discussed for explanation purposes herein). As noted above, it would be advantageous to combine such switches without blocking the full input bandwidth or blocking the full output bandwidth of the combined switches.
FIG. 2 shows 2.times.2 ATM switch elements which are connected together. The resulting combined switch element has the same switching ability as the switch shown in FIG. 1. A simple combination of switches does not increase the switching function.
FIG. 3 shows a combination of four switches such as the switch shown in FIG. 1. The switches are provided in a column and row formation. The first column are switches providing the input. The second column (or last column) are switches which provide the output. The rows include an upper row or first row and lower row or second row. A person of ordinary skill in the art will appreciate that physically the switches do not have to be positioned this way relative to each other as long as the connections are as shown. Nevertheless, a discussion of an input column or input segment, an output column or output segment and rows of the combined switch, facilitates explanation.
In the combined switch of FIG. 3, switches such as FIG. 1 are combined to provide four inputs I.sub.1, I.sub.2, I.sub.3, and I.sub.4 and four outputs O.sub.1, O.sub.2, O.sub.3, and O.sub.4. This appears to provide a scaling or increase in switching function. However, the combined switch of FIG. 3 is blocking because the following input to output streams will be blocking for fifty percent of the time. Specifically, I.sub.1 .fwdarw.O.sub.3 ; I.sub.2 .fwdarw.O.sub.4 ; I.sub.3 .fwdarw.O.sub.1 ; I.sub.4 .fwdarw.O.sub.2. This can be appreciated as in the combined switch of FIG. 3 a switch element of the top row of the input section (with inputs I.sub.1 and I.sub.2) only has one connection to the switch in the output section of the bottom row (with output O.sub.3 and output O.sub.4). If two input streams are to flow from the switch element of the input section top row to the output section bottom row, one of these streams is blocked.
Further, in providing a multistage switch a problem arises as to (a) introducing out of order cells and (b) introducing internal bottlenecks caused by static connection routing.
The standard solution for this problem involves buffered switch stages and a final step to put the cells back in order (causing substantial extra delay and cost). A further solution involves a fixed routing of connections which necessarily causes congestion at individual connections.